import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

public class MST {

	// kruskal's
	public static Collection<Edge> kruskals(Graph g) {
		ArrayList<Edge> edges = new ArrayList<>(g.getEdgeList());
		Collections.sort(edges);
		DisjointSets<Vertex> ds = new DisjointSets<>(g.getVertices());
		ArrayList<Edge> result = new ArrayList<>();
		ArrayList<Vertex> vertices = new ArrayList<>(g.getVertices());
		Vertex from = null;
		for (Edge minimum : edges) {
			from = minimum.getU();
			Vertex to = minimum.getV();
			if (!ds.sameSet(from, to)) {
				ds.merge(from, to);
				result.add(minimum); }
		}
		
		boolean valid = false;
		for (int i=0;i<vertices.size();i++)
			if (ds.sameSet(from, vertices.get(i)))
				valid = true;
			else {
				valid = false;
				break; }
		if (valid) return result;
		return null; }
	
	//prim's
	public static Collection<Edge> prims(Graph g, int start){
		ArrayList<Edge> result = new ArrayList<>();
		ArrayList<Edge> edges = new ArrayList<>(g.getEdgeList());
		Collections.sort(edges);
		ArrayList<Vertex> vertex = new ArrayList<>(g.getVertices());
		ArrayList<Vertex> look = new ArrayList<>();
		Vertex s = new Vertex(start);
		look.add(s);
		int i=0;
		while (look.size()!=vertex.size()){
			while (i<edges.size()) {
				for (Vertex current: look){
					if (current.equals(edges.get(i).getU()) && !look.contains(edges.get(i).getV())){
						result.add(edges.get(i));
						look.add(edges.get(i).getV());
						//edges.remove(i);
						i=-1;
						break;}
				}
				i++; }
			if (look.size()!=vertex.size() && i==edges.size()) return null;
			if (i==edges.size()) return result;
		}

		return null; }
	
}